// 链式结构：表示队列 
typedef  int  QDataType;

typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* cur = (QNode*)malloc(sizeof(QNode));
     
	if (cur == NULL)
	{
		perror("malloc ");
		exit(-1);
	}
	cur->data = data;
	cur->next = NULL;

	if (q->rear == NULL)
	{
		q->front = q->rear = cur;
	}
	else
	{
		q->rear->next = cur;
		q->rear = cur;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->front->next == NULL)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QNode* cur = q->front->next;
		free(q->front);
		q->front = cur;
	}
	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);

	return q->front->data;


}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);

	return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL && q->rear == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);

	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}

	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}


typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//初始化
MyStack* myStackCreate()
{
       MyStack*obj = (MyStack*)malloc(sizeof(MyStack));

       QueueInit(&obj->q1);
       QueueInit(&obj->q2);
        
       return obj;
}

void myStackPush(MyStack* obj, int x) 
{   
    if( !QueueEmpty(&obj->q1 ) )
     QueuePush(&obj->q1, x );//吧元素先压入q1
    else
     QueuePush(&obj->q2, x );
}

int myStackPop(MyStack* obj) 
{
   Queue *Nul =&obj->q1,*Nnul=&obj->q2;
   if(!QueueEmpty(&obj->q1))
   {
       Nul= &obj->q2;
       Nnul=&obj->q1;
   }
   while(QueueSize(Nnul)>1)
   {
      QueuePush(Nul,QueueFront(Nnul));
      QueuePop(Nnul);
   }
   int tmp =QueueFront(Nnul);
   QueuePop(Nnul);
   return tmp;
}

int myStackTop(MyStack* obj) 
{
   if(!QueueEmpty(&obj->q1))
   return QueueBack(&obj->q1);
   else
   return QueueBack(&obj->q2);
}

bool myStackEmpty(MyStack* obj)
{
     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) 
{
     QueueDestroy(&obj->q1);
     QueueDestroy(&obj->q2);
     free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/